package com.warningrc.demo;

import java.util.ArrayList;
import java.util.Stack;


public class DFS_5 {
    // 定义图节点类
    static class Node {
        // 节点的值
        int value;
        // 存储该节点的邻接节点列表
        ArrayList<Node> neighbors;

        Node(int value) {
            this.value = value;
            this.neighbors = new ArrayList<>();
        }
    }

    // 寻找图中两点之间所有路径的方法，接受起始节点和目标节点作为参数
    public static ArrayList<ArrayList<Integer>> findAllPaths(Node start, Node end) {
        ArrayList<ArrayList<Integer>> allPaths = new ArrayList<>();
        Stack<Node> stack = new Stack<>();
        ArrayList<Integer> path = new ArrayList<>();
        boolean[] visited = new boolean[100]; // 假设图中最多有100个节点，根据实际情况调整大小
        findAllPathsUtil(start, end, stack, path, visited, allPaths);
        return allPaths;
    }

    // 辅助的深度优先搜索方法，用于寻找从起始节点到目标节点的所有路径
    private static void findAllPathsUtil(Node current, Node end, Stack<Node> stack, ArrayList<Integer> path, boolean[] visited, ArrayList<ArrayList<Integer>> allPaths) {
        stack.push(current);
        visited[current.value] = true;
        path.add(current.value);
        if (current == end) {
            // 如果找到目标节点，将当前路径添加到所有路径列表中
            allPaths.add(new ArrayList<>(path));
        }
        for (Node neighbor : current.neighbors) {
            if (!visited[neighbor.value]) {
                findAllPathsUtil(neighbor, end, stack, path, visited, allPaths);
            }
        }
        stack.pop();
        visited[current.value] = false;
        path.remove(path.size() - 1);
    }
}